#!/usr/bin/python

class QuickUnion(object):

  def __init__(self, num_objects):
    self.id_list = range(num_objects)

  def GetRoot(self, object_id):
    while not self.id_list[object_id] == object_id:
      object_id = self.id_list[object_id]
    return object_id

  def connected(self, p, q):
    return self.GetRoot(p) == self.GetRoot(q)

  def union(self, p, q):
    p_root = self.GetRoot(p)
    q_root = self.GetRoot(q)
    self.id_list[p_root] = q_root

def main():
  num_objects = 10
  qu = QuickUnion(num_objects)
  qu.union(1, 3)
  qu.union(1, 9)
  print '1, 9 connected: ', qu.connected(1, 9)
  print 'pos: ', range(num_objects)
  print 'ids: ', qu.id_list

if __name__ == '__main__':
  main() 
